package Leetcode.lc056;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;

/***
 *
 56. 合并区间
 中等
 相关标签
 premium lock icon
 相关企业
 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 */
public class Sloution {
    //排序做法

    /***
     * 合并区间，重点在于lambda的使用
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        //左端点排序
        Arrays.sort(intervals,(p,q)->p[0]-q[0]);
        //创建临时
        ArrayList<int[]> list = new ArrayList<>();
        for(int[] p:intervals){
            int m=list.size();
            if(m>0 && p[0]<=list.get(m-1)[1]){
                //合并区间
                list.get(m-1)[1]=Math.max(p[1],list.get(m-1)[1]);
            }else{
                list.add(p);
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        int[][] test={{1,3},{2,6},{8,10},{15,18}};
        int[][] merge = sloution.merge(test);
        System.out.println(merge);
    }

}
